Įkurtas 1932 m. Lubango mieste.[1] Asociaciją 1932 m. vasario 27 d. Įkūrė naujakuriai iš Portugalijos. „Benfica do Lubango“ buvo 37-asis Portugalijos klubo Lisabonos „Benfica“ padalinys.
Vykdant antikolonijinę politiką šalyje, po Angolai tapus nepriklausoma valstybe 1975 m., klubas buvo pavadintas „Clube Desportivo da Chela“. Po 1989 m. sezono pavadinimą susigražino.
„Benfica do Lubango“ nėra iškovojusi nė vieno šalies titulo. Savo laiku buvo nuolatinis aukščiausios Angolos lygos - „Girabola“ - dalyvis. Būta eilės iškritimų iš eilito diviziono. 2006 m. komanda pasiekė ketvirtąją vietą Giraboloje, o 2008 m. sezoną baigė 14-oje, paskutinėje tuo metu vietoje, o tai reiškė dar vieną iškritimą. Pakilo į Girabola2009 m., o iškrito 2010 m.
Klubas 2013 m. vėl pateko į Girabola, bet kitą sezoną buvo 15-oje vietoje ir vėl buvo perkeltas į antrą divizioną.
2018/19 m. sezone Segundona pirmenybėse (antroje pakopoje) buvo antri, tačiau klubas buvo nušalintas nuo dalyvavimo Girabola.